package com.demo.datastructure.reorder.mergeSort;

/**
 * @description: 归并排序
 * @author: ljr
 * @time: 2021/5/4 16:15
 * @since： 1.0
 */
public class MyMergeSort {

    public static void mergeSort(int[] args, int n){
        mergeSortC(args,0,n-1);
    }

    private static void mergeSortC(int[] args, int p, int r) {
        if(p >= r) return;
        int q = (p+r)/2;
        mergeSortC(args,p,q);
        mergeSortC(args,q+1,r);
        merge(args,p,r,q);
    }

    private static void merge(int[] args, int p, int r, int q) {
        int i = p;
        int j = q+1;
        int k = 0;

        int[] tmp =  new int[r-p+1];
        while(i <= q &&  j <= r){
            if(args[i] <= args[j]){
                tmp[k++] = args[i++];
            }else{
                tmp[k++] = args[j++];
            }
        }

        int start = i;
        int end = q;
        if(j <= r){
            start = j;
            end = r;
        }

        while(start <= end){
            tmp[k++] = args[start++];
        }

        for(i =0; i < r-p+1; i++){
            args[p+i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{11,8,3,9,7,1,2,5};
        MyMergeSort.mergeSort(nums,8);
        for(int num : nums){
            System.out.println(num);
        }
    }

}
